SICP 习题 1.9

Exercise 1.9.  Each of the following two procedures defines a method for adding two positive integers in terms of the procedures inc, which increments its argument by 1, and dec, which decrements its argument by 1.

练习题 1.9. 以下两个过程都定义了一个方法，用于在 inc 和 dec 这两个过程的基础上，将两个正整数相加，其中 inc 将其参数加1，dec 将其参数减 1。

Using the substitution model, illustrate the process generated by each procedure in evaluating (+ 4 5). Are these processes iterative or recursive?

使用替换模型，说明评估（+ 4 5）时每个过程生成的过程。这些过程是迭代的还是递归的？

#lang racket

(define (inc x)
  (+ x 1))

(define (dec x)
  (- x 1))

(define (p a b)
  (if (= a 0)
      b
      (inc (p (dec a) b))))

(define (++ a b)
  (if (= a 0)
      b
      (++ (dec a) (inc b))))

(displayln (p 2 3))
(displayln (++ 2 3))

分析

让我们逐步分析这两个过程 (+) 和 (++) 是如何计算 (+ 4 5) 的，并判断它们生成的过程是递归的还是迭代的。

过程 1: (+ a b) 使用 p 代替 +

定义如下：

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

评估 (+ 4 5)

  1. 计算 (+ 4 5)，由于 a 不等于 0，我们进入 else 部分，计算 (inc (+ (dec 4) 5))
  2. 计算 (dec 4) 得到 3，所以我们要计算 (inc (+ 3 5))
  3. 计算 (+ 3 5)，由于 a 不等于 0，我们进入 else 部分，计算 (inc (+ (dec 3) 5))
  4. 计算 (dec 3) 得到 2，所以我们要计算 (inc (+ 2 5))
  5. 计算 (+ 2 5)，由于 a 不等于 0，我们进入 else 部分，计算 (inc (+ (dec 2) 5))
  6. 计算 (dec 2) 得到 1，所以我们要计算 (inc (+ 1 5))
  7. 计算 (+ 1 5)，由于 a 不等于 0，我们进入 else 部分，计算 (inc (+ (dec 1) 5))
  8. 计算 (dec 1) 得到 0，所以我们要计算 (inc (+ 0 5))
  9. 现在计算 (+ 0 5)，由于 a = 0，返回 b = 5
  10. 返回的结果传递回第 8 步，得到 (inc 5)，即 6
  11. 返回的结果传递回第 7 步，得到 (inc 6)，即 7
  12. 返回的结果传递回第 6 步，得到 (inc 7)，即 8
  13. 返回的结果传递回第 5 步，得到 (inc 8)，即 9
  14. 返回的结果传递回第 4 步，得到 (inc 9)，即 10
  15. 返回的结果传递回第 3 步，得到 (inc 10)，即 11
  16. 返回的结果传递回第 2 步，得到 (inc 11)，即 12
  17. 返回的结果传递回第 1 步，得到 (inc 12)，即 13

结果为 13。这个过程在每一层递归中都有未完成的计算，因此生成了一个递归过程。

过程 2: (++ a b)

定义如下：

(define (++ a b)
  (if (= a 0)
      b
      (++ (dec a) (inc b))))

评估 (++ 4 5)

  1. 计算 (++ 4 5)，由于 a 不等于 0，我们进入 else 部分，计算 (++ (dec 4) (inc 5))
  2. 计算 (dec 4) 得到 3，(inc 5) 得到 6，所以计算 (++ 3 6)
  3. 计算 (++ 3 6)，由于 a 不等于 0，我们进入 else 部分，计算 (++ (dec 3) (inc 6))
  4. 计算 (dec 3) 得到 2，(inc 6) 得到 7，所以计算 (++ 2 7)
  5. 计算 (++ 2 7)，由于 a 不等于 0，我们进入 else 部分，计算 (++ (dec 2) (inc 7))
  6. 计算 (dec 2) 得到 1，(inc 7) 得到 8，所以计算 (++ 1 8)
  7. 计算 (++ 1 8)，由于 a 不等于 0，我们进入 else 部分，计算 (++ (dec 1) (inc 8))
  8. 计算 (dec 1) 得到 0，(inc 8) 得到 9，所以计算 (++ 0 9)
  9. 现在 a = 0，返回 b = 9

最终结果为 9。在每一步递归中，(++ a b) 的计算完全依赖于调用参数的值而不是层层嵌套的计算，这生成了一个迭代过程，因为递归调用没有生成未完成的计算，消耗的空间和时间是恒定的。

结论

本文作者：Maeiee

本文链接：SICP 习题 1.9

版权声明：如无特别声明，本文即为原创文章，版权归 Maeiee 所有，未经允许不得转载！

喜欢我文章的朋友请随缘打赏，鼓励我创作更多更好的作品！